package classics.DFS;

/**
 * EX200 岛屿数量
 * 深度优先和广度优先的差别、如何计算时间空间复杂度？
 * 若求形状不同的岛屿的数量呢？
 */
public class EX200 {
    int res = 0;
    int m;
    int n;
    public int numIslands(char[][] grid) {
        if(grid.length==0){
            return 0;
        }
        m = grid.length;
        n = grid[0].length;

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j);
                    res++;
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid,int i,int j){
        if(i<0||i>=m||j<0||j>=n||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}
